package class03;

/**
 * 二分, 只要确定一侧有就可以使用二分
 *
 * 一个数组, 存在局部最小(相邻的数不相等), 找到一个局部最小(可能有多个, 找到一个即可)
 * 特殊的如凹函数 或 单调函数
 *
 * 思路: 先看两端 假设头比头+1的小, 那么头就是一个局部最小
 * 假设尾比尾-1的小, 那么尾就是一个局部最小
 * 否则中间的数可以构成凹函数, 找到一个数比两边的数都小就是局部最小
 */
public class Code04_BSAwesome {

  // arr 整体无序
  // arr 相邻的数不相等！
  public static int oneMinIndex(int[] arr) {
    if (arr == null || arr.length == 0) {
      return -1;
    }
    int N = arr.length;
    if (N == 1) {
      return 0;
    }
    // 只有两个数的比较情况
    // 0位置比1小
    if (arr[0] < arr[1]) {
      return 0;
    }
    // 1位置比0小
    if (arr[N - 1] < arr[N - 2]) {
      return N - 1;
    }
    int L = 0;
    int R = N - 1;
    // L...R 肯定有局部最小
    // L < R - 1, 保障while循环中有3个数
    while (L < R - 1) {
      int mid = (L + R) / 2;
      if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
        //比两边都更小, 那么该值即为局部最小
        return mid;
      } else {
        if (arr[mid] > arr[mid - 1]) {
          //比左边大, 那么去左边找局部最小
          R = mid - 1;
        } else {
          //比右边大, 那么去右边找局部最小
          L = mid + 1;
        }
      }
    }
    //从while循环中出来, 表示只有2个数, 那么只需要判断L 和 R的大小即可
    return arr[L] < arr[R] ? L : R;
  }

  // 生成随机数组，且相邻数不相等
  // 1 2 3 1 2 3
  public static int[] randomArray(int maxLen, int maxValue) {
    int len = (int) (Math.random() * maxLen);
    int[] arr = new int[len];
    if (len > 0) {
      //先生成 0 位置的数值
      arr[0] = (int) (Math.random() * maxValue);
      for (int i = 1; i < len; i++) {
        do {
          //从 1 位置开始随机生成
          arr[i] = (int) (Math.random() * maxValue);
        }
        //如果后生成的和前面生成的相等, 那么重新生成
        while (arr[i] == arr[i - 1]);
      }
    }
    return arr;
  }

  // 也用于测试当前数是否是一个局部最小的数
  public static boolean check(int[] arr, int minIndex) {
    if (arr.length == 0) {
      return minIndex == -1;
    }
    int left = minIndex - 1;
    int right = minIndex + 1;
    //左边比当前位置大
    boolean leftBigger = left >= 0 ? arr[left] > arr[minIndex] : true;
    //右边比当前位置大
    boolean rightBigger = right < arr.length ? arr[right] > arr[minIndex] : true;
    return leftBigger && rightBigger;
  }

  public static void printArray(int[] arr) {
    for (int num : arr) {
      System.out.print(num + " ");
    }
    System.out.println();
  }

  public static void main(String[] args) {
    int maxLen = 100;
    int maxValue = 200;
    int testTime = 1000000;
    System.out.println("测试开始");
    for (int i = 0; i < testTime; i++) {
      int[] arr = randomArray(maxLen, maxValue);
      int ans = oneMinIndex(arr);
      if (!check(arr, ans)) {
        printArray(arr);
        System.out.println(ans);
        break;
      }
    }
    System.out.println("测试结束");
  }
}
